#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_map<string, int> vis;
        unordered_map<string, int> hash;
        string st = "ACGT";
        queue<string> q;
        q.push(startGene);
        hash[startGene];
        for (auto& s : bank)
            vis[s];
        int ret = 0;
        if (startGene == endGene)
            return 0;
        if (vis.count(endGene) == 0)
            return -1;
        while (q.size()) {
            ret++;
            int n = q.size();
            for (int j = 0; j < n; j++) {
                string tmp = q.front();
                q.pop();
                for (int i = 0; i < tmp.size(); i++) {
                    char ch = tmp[i];
                    for (int k = 0; k < 4; k++) {
                        tmp[i] = st[k];
                        if (tmp == endGene)
                            return ret;
                        if (vis.count(tmp) && hash.count(tmp) == 0)
                            q.push(tmp), hash[tmp];
                    }
                    tmp[i] = ch;
                }
            }
        }
        return -1;
    }
};